class Solution {
public:
    vector<vector<string> > res;
    bool isvalid(int row,int col,vector<string>& ans,int n){
      for(int i = 0;i < row;i++){
        if(ans[i][col] == 'Q'){
          return false;
        }
      }
      for(int i = row,j = col;i >= 0 && j >= 0;i--,j--){
        if(ans[i][j] == 'Q'){
          return false;
        }
      }
      for(int i = row,j = col;i >= 0 && j < n;i--,j++){
        if(ans[i][j] == 'Q'){
          return false;
        }
      }
       return true;
    }
    void backtracking(int n,int cur,vector<string >& ans){
      if(cur >= n){
        res.push_back(ans);
        return;
      }
      for(int i = 0;i < n;i++){
        if(isvalid(cur,i,ans,n)){
          ans[cur][i] = 'Q';
          backtracking(n,cur+1,ans);
          ans[cur][i] = '.';
        }
      }
    }
    vector<vector<string>> solveNQueens(int n) {
      vector<string> ans(n,string(n,'.'));
      backtracking(n,0,ans);
      return res;
    }
};
